#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

class Solution {
private:
    struct word_node {
        bool end = false;
        bool added = false;
        word_node* dict[26] = {nullptr};
    };
    vector<vector<bool>> visited;
    word_node word_head;
    vector<vector<char>>* board;
    vector<string> ans;
    void forward(int i, int j, word_node* node, string his) {
        if (i < 0 || j < 0 || i == board->size() || j == board->at(0).size() || visited[i][j]) {
            return;
        }
        if (node->dict[board->at(i)[j] - 'a'] == nullptr) {
            return;
        }
        node = node->dict[board->at(i)[j] - 'a'];
        his.push_back(board->at(i)[j]);
        if (node->end && !node->added) {
            ans.push_back(his);
            node->added = true;
        }
        visited[i][j] = true;
        forward(i + 1, j, node, his);
        forward(i - 1, j, node, his);
        forward(i, j + 1, node, his);
        forward(i, j - 1, node, his);
        visited[i][j] = false;
        his.pop_back();
    }
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        for (string word : words) {
            word_node* node = &word_head;
            for (char item : word) {
                if (node->dict[item - 'a'] == nullptr) {
                    node->dict[item - 'a'] = new word_node;
                }
                node = node->dict[item - 'a'];
            }
            node->end = true;
        }
        visited.assign(board.size(), vector<bool>(board[0].size(), false));
        this->board = &board;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                forward(i, j, &word_head, "");
            }
        }
        return ans;
    }
};

int main() {
    vector<vector<char>> input_board = {{'a', 'a'}};
    vector<string> input_word = {"aaa"};
    Solution solution;
    vector<string> output = solution.findWords(input_board, input_word);
    for (string item : output) {
        cout << item << endl;
    }
    return 0;
}